package random_test;

import java.util.*;

public class Test_10_12 {

    //438. 找到字符串中所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] hash1 = new int[26];       // 哈希表，记录p中每个字母出现的次数
        int[] hash2 = new int[26];       // 记录 s 中每个字母出现的次数
        for(int i = 0; i < p.length(); i++)
            hash1[p.charAt(i) - 97]++;
        for(int left = 0, right = 0, valid = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            // 进窗口
            if(hash2[ch - 97] < hash1[ch - 97]) valid++;
            hash2[ch - 97]++;
            // 判断是否需要出窗口
            while(right - left + 1 > p.length()) {
                char out = s.charAt(left++);
                if(hash1[out - 97] != 0 && hash2[out -97] <= hash1[out - 97]) valid--;
                hash2[out - 97]--;
            }
            // 更新结果
            if(valid == p.length()) ret.add(left);
        }
        return ret;
    }


    //904. 水果成篮
    public int totalFruit(int[] fruits) {
        int[] count = new int[fruits.length + 1];   // 记录每个种类水果在篮子的个数
        int ret = 0;
        for(int left = 0, right = 0, kinds = 0; right < fruits.length; right++) {
            int in = fruits[right];
            if(count[in] == 0) kinds++;
            count[in]++;    // 入窗口
            // 判断是否需要出窗口
            while(kinds > 2) {
                int out = fruits[left++];
                if(count[out] == 1) kinds--;
                count[out]--;
            }
            ret = Math.max(ret, right - left + 1);      // 更新结果
        }
        return ret;
    }


    //1658. 将 x 减到 0 的最小操作数
    // 等同于求 数组所有元素的和 - x == target的数组区间的最大长度
    public int minOperations(int[] nums, int x) {
        int ret = -1, sum = 0;
        for(int i = 0; i < nums.length; i++)
            sum += nums[i];
        if(sum < x) return -1;     // 判断是否可能存在返回数
        int target = sum - x;
        sum = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            sum += nums[right];         // 进窗口
            // 判断是否需要出窗口
            while(sum > target) {
                sum -= nums[left++];
            }
            if(sum == target) ret = Math.max(ret, right - left + 1);
        }
        if(ret == -1) return -1;
        return nums.length - ret;
    }


    //1004. 最大连续1的个数 III
    public int longestOnes(int[] nums, int k) {
        int ret = 0;
        for(int left = 0, right = 0, zero = 0; right < nums.length; right++) {
            if(nums[right] == 0) zero++;    // 入窗口
            // 判断是否出窗口
            while(zero > k) {
                if(nums[left] == 0) zero--;
                left++;
            }
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}
